package cn.idu.ismik

import kotlin.math.min


/**
 * 凑零钱问题：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，
 * 问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
 */
fun main() {
    val arr = intArrayOf(1, 2, 5)
    val amount = 6
    println("[1,2,5] amount: $amount - ret: ${coinChange(arr, amount)}")
    println("[1,2,5] amount2: $amount - ret: ${coinChange2(arr, amount)}")
}

fun coinChange(coins: IntArray, amount: Int): Int {
    fun dp(n: Int): Int {
        //base case
        if (n == 0) return 0

        if (n < 0) return -1
        var res = Int.MAX_VALUE
        for (coin in coins) {
            val subPloblem = dp(n - coin)
            if (subPloblem == -1) continue
            res = min(res, 1 + subPloblem)
        }
        println("$res, $n")
        return if (res == Int.MAX_VALUE) -1 else res
    }
    return dp(amount)
}


fun coinChange2(coins: IntArray, amount: Int): Int {//消除重叠子问题，带备忘录递归
    val memo = HashMap<Int, Int>()
    fun dp(n: Int): Int {
        if (memo.containsKey(n)) return memo[n]!!
        //base case
        if (n == 0) return 0
        if (n < 0) return -1
        var res = Int.MAX_VALUE
        for (coin in coins) {
            val subPloblem = dp(n - coin)
            if (subPloblem == -1) continue
            res = min(res, 1 + subPloblem)
        }
        println("$res, $n")
        memo[n] = if (res == Int.MAX_VALUE) -1 else res
        return memo[n]!!
    }
    return dp(amount)
}
